package 每日一题OJ;

/**
 * @author shy_black
 * @date 2019/8/24 14:56
 * @Description:
 */
public class _395__至少有K个重复字符的最长子串 {
    public int longestSubstring(String s, int k) {
        int len = s.length();
        if(len == 0 || k > len) return 0;
        if(k < 2) return len;

        return count(s.toCharArray(),k,0,len-1);
    }
    //利用分治的思想去解决，在小问题中求解，最后解决大问题
    public static int count(char[] s,int k,int l ,int r) {
        if(r-l+1 < k)
            return 0;
        int[] arr = new int[26];
        for(int i = l;i <= r;i++) {
            arr[s[i] - 'a']++;
        }
        while(r-l+1 >= k && arr[s[l] - 'a'] < k) l++;
        while(r-l+1 >= k && arr[s[r] - 'a'] < k) r--;
        if(r-l+1 < k)
            return 0;
        for(int i = l;i <= r;i++) {
            if(arr[s[i] - 'a'] < k)
                return Math.max(count(s,k,l,i-1),count(s,k,i+1,r));
        }
        return r-l+1;

    }
}